#define _CRT_SECURE_NO_WARNINGS 1

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

struct ListNode 
{
    int val;
    struct ListNode* next;
};

struct ListNode* merge(struct ListNode* head1, struct ListNode* head2) 
{
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(dummyHead);
    struct ListNode* temp = dummyHead, * temp1 = head1, * temp2 = head2;
    while (temp1 != NULL && temp2 != NULL) {
        if (temp1->val <= temp2->val) {
            temp->next = temp1;
            temp1 = temp1->next;
        }
        else {
            temp->next = temp2;
            temp2 = temp2->next;
        }
        temp = temp->next;
    }
    if (temp1 != NULL) {
        temp->next = temp1;
    }
    else if (temp2 != NULL) {
        temp->next = temp2;
    }
    struct ListNode* newhead = dummyHead->next;
    free(dummyHead);
    return newhead;
}

struct ListNode* toSortList(struct ListNode* head, struct ListNode* tail) {
    if (head == NULL) {
        return head;
    }
    if (head->next == tail) {
        head->next = NULL;
        return head;
    }
    struct ListNode* slow = head, * fast = head;
    while (fast != tail) {
        slow = slow->next;
        fast = fast->next;
        if (fast != tail) {
            fast = fast->next;
        }
    }
    struct ListNode* mid = slow;
    return merge(toSortList(head, mid), toSortList(mid, tail));
}

struct ListNode* sortList(struct ListNode* head) 
{
    return toSortList(head, NULL);
}

int main()
{
    struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    assert(n1 && n2 && n3 && n4);
    n1->val = 3;
    n2->val = 2;
    n3->val = 4;
    n4->val = 1;

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = NULL;
    n1 = sortList(n1);
    
    struct ListNode* cur = n1;
    while (cur)
    {
        printf("%d->", cur->val);

        cur = cur->next;
    }
    return 0;
}
